1. Field of the invention
The present invention relates to computer graphics, and in particular, discloses apparatus that alleviates the need for large image stores.
2. Description of the related arts
High resolution full color graphics images require a massive amount of data. For an image the size of an A3 page, having a resolution of 400 dots per inch (dpi), approximately 96 MBytes are required. Such a memory size creates two problems. The first problem is the cost and time involved in the storage and transmission of 96 MBytes of data per image, and the second problem is the cost of 96 MBytes of semiconductor memory required for an image store that is necessary for generating and manipulating graphics images.
Some aspects of the prior art will now be described with reference to FIGS. 1A and 1B, and 2A and 2B.
FIG. 1A shows schematically a computer based graphics system 10 which has graphics commands arranged within a page display list (PDL) 1. The commands of the PDL 1 are high level commands that describe certain images to be created by the user such as DRAW CIRCLE or WRITE TEXT for example, the type of commands and language representation not being important for this illustration. When the graphics image is to be formed, the commands in the PDL 1 are interpreted 4 and the image is created sequentially on a pixel-by-pixel basis and stored in a full page memory 2. Once the entire image is stored in the memory 2 it can be printed by outputting 5 the stored data to a printer 3.
The formation of pixel image data from object based data is known in the art as rendering. As such, rendering opaque images involves writing pixel image data into memory. However, when images are transparent, it is necessary to composite. Compositing involves the combining of pixel images, generally by controlling the proportion of two or more source images in a destination or composited image. Accordingly, rendering transparent images involves compositing newly rendered objects with existing pixel image data.
The realization of FIG. 1B shows a full color graphics system 10 having an image store 6 having a capacity of 96 MBytes capable of storing a full color image for an A3 page. The image store 6 includes 1 byte of semiconductor memory for each of red, green, and blue (RGB) components for every pixel of the image. As seen in FIG. 1B, the size of an A3 page is 4,632.times.6,480 pixels for an image density of 400 dpi. The image store 6 is connected via a 24 bit RGB bus 8 to a system bus 7 which links the store 6 with a computer 11, a hard disk data storage unit 12 and a data transmission unit 13 for interconnection with other devices. The computer 11 performs calculations necessary to form the graphics image under the interpretation step 4 of FIG. 1A. The image store 6 is also connected to a converter 14 which converts RGB data into MCYK (magenta, cyan, yellow and black) data ready for reproduction preferably on a color laser printer 15 such as that included in the CANON (Registered Trade Mark) Color Laser Copier available from Canon KK of Japan. Reproduction on a video display (not shown illustrated) can also be readily achieved in a known manner.
The general arrangement of FIGS. 1A and 1B is currently cost effective for full color images of up to approximately 2 million pixels (6 MBytes). Pixel mapped image stores are also cost effective for binary images up to 32 million pixels, where only one bit per pixel is required, giving a total of 4 MBytes. However, for large color images, the memory requirement becomes excessive as seen in the 96 MBytes shown in FIG. 1. While this provides no particular technical problems, it is very expensive. The image store 6 is generally manufactured from semiconductor memories, generally being dynamic random access memory (DRAM) which costs approximately 0.5 millicents per bit (as of the date of this application). This represents almost $4,000 of direct component costs for the store 6 within the graphics system 10. In many systems, an image store of this size represents the single largest cost element.
Furthermore, the prior art system of FIG. 1B requires 96 MBytes of data storage for each image within the data storage unit 12, which is generally a hard disk drive. Also, 96 MBytes of information must be transferred from the storage device 12 to the image store 6 for each image to be printed on the printer 15. Also, the computer 11 must calculate 32 million pixels, each with 24 bits of information, in order to generate a single A3 image. The calculation of such images is inherently slow.
Suitable technology is currently available to alleviate the problem of massive file storage requirements for images. This technology is known as image compression, and in particular, Adaptive Discrete Cosine Transform (ADCT) compression. This technology can achieve compression ratios of 25:1 with negligible image quality loss on photographic images. Those skilled in the art will note that there is substantial quality loss with small point sized text. The use of ADCT compression reduces the data storage and transmission requirements from 96 MBytes for a 400 dpi A3 image to approximately 4 MBytes. The most suitable system currently available is for ADCT processing that was devised by the CCITT/ISO Joint Photographic Expert's Group (JPEG) based on Discrete Cosine Transform and Huffman encoding processes and published in ISO/IEO JTC1/SC2/WG8 JPEG Technical Specification Rev 5 Jan. 16, 1990. An ADCT processor system has been implemented in silicon by C-Cube Microsystems as the CL550B device.
FIGS. 2A and 2B show a graphics system 20, similar to that of FIG. 1, that uses ADCT compression for storage of images.
In FIG. 2A, a PDL 21 is provided in a manner similar to that of FIG. 1A. However, rather than directly calculating the image, the entire PDL 21 is compiled 24 to provide a display list 22 of low level commands. The image is realized by rendering 25. The display list 22 in bands into a strip buffer 23 whereby the image data stored in the strip buffer 23 represents a strip or band of the total image. As each strip is calculated (rendered) it can be printed directly by a printer 15 or compressed by a compressor 27 for storage in a (compressed) image memory 29. Data from the memory 29 can be expanded by an expander 28 for printing.
The graphics system 20 of FIG. 2B utilizes an ADCT processor 30 including compression and expansion functions connected to a compressed image store 31 having a capacity of 4 MBytes. A virtual image store 33 formed of a hard disk drive acts as a permanent store of a full image (96 MBytes).
The system 20 also includes a strip buffer 23 which is used to store a band of the image as it is calculated by the computer 11. The size of the strip buffer 23 is a compromise between cost and speed. A larger strip buffer is more expensive, but reduces the number of bands which must be calculated and therefore the time taken to calculate the image using conventional 2D object graphics techniques.
In operation, sections or bands of the image are calculated by the computer 11 and written into the strip buffer 23. This is achieved using object based display lists generally retained in the data storage 12 which are traversed for each band to be calculated. Such an operation is supported by many graphics systems, for example, in the Postscript language it can be achieved using the BANDDEVICE function.
When the strip buffer 23 is full, the calculated data is written into the virtual image store 33 or directly into the compressed image store 31 via the ADCT processor 30. This is repeated until the entire image is calculated. If the strip buffer 23 has a capacity of 1 MByte, and the image to be calculated comprises 96 MBytes, then 96 bands are required to be calculated.
Once the entire image has been calculated, if written onto the disk virtual image store 33, it is read from the store 33 and compressed by the ADCT processor 30 and written into the compressed image store 31.
When it is required to print any image, it is required to transfer the data from the virtual image store 33 to the compressed image store 31. The compressed image data is then read from the store 31 and decompressed by the ADCT processor 30. This is then output from the processor 30 to the converter 14 for printing by the printer engine 15. The CL550B ADCT processor device includes parallel MCYK outputs, and in some circumstances it is possible to omit the RGB to MCYK conversion and replace it with a simple data multiplexer.
In the system of FIG. 2B, the ADCT processor 30 is required because, when the entire image is stored in the virtual image store 33, which is a hard disk drive, it cannot be read rapidly enough to drive currently available color laser printers, such as the Canon CLC500. Such printers require 4 passes of color data (magenta, cyan, yellow and black) each of approximately 32 MBytes, at a data rate of 13.35 MBytes per second. If the data were to be stored on the disk in RGB format as indicated in FIG. 2B, then the data would have to be read from the disk four times at a rate of 40.05 MBytes per second (RGB at 13.35 MBytes per second each) and converted into MCYK. This needs to be done for every copy of every page to be printed. Such a data rate cannot be achieved using currently available cost effective hard disk drives. This problem is overcome using a complete image buffer, which in this case, is achieved using a compressed image store of 4 MBytes.
The graphics system 20 of FIG. 2 has serious limitations in image calculation speed. The image generation time cannot be less than the time taken to transfer the entire image into and out the virtual image store 33. Most currently available cost effective disk drives are limited to continuous transfer rates of less than 1 MByte per second. For 96 MBytes to be transferred into and out of an appropriately configured disk drive, a theoretical minimum time of 3.2 minutes is required. In practice, the time required to perform this function is much greater.
Another significant speed problem is the extra time taken to traverse the display list for each band (96 times in this case), rather than simply to draw each object. Also, page complexity is limited by the amount of display list memory (RAM within the computer 11).
As well as the above problems, the system of FIG. 2 does not remove the necessity to calculate every pixel of the image. For example, if 100 pixels can be calculated every millisecond, the time required to calculate 32 million pixels is at least 320 seconds. With other associated overheads, the time required to calculate a full color A3 page is generally more than 10 minutes.